//
// Created by 紫霄 on 2020/5/14.
//

#ifndef LEETCODE_34_H
#define LEETCODE_34_H
#include <stack>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) { stack<TreeNode *> nodes; }
};
class Solution {
public:
  vector<vector<int>> pathSum(TreeNode *root, int sum) {
    vector<vector<int>> ans;
    if (!root)
      return ans;
    vector<int> curLine;
    checkNowLevel(root, sum, 0, ans, curLine);
  }
  void checkNowLevel(TreeNode *root, int sum, int nowSum,
                     vector<vector<int>> &ans, vector<int> &curLine) {
    nowSum += root->val;
    curLine.emplace_back(root->val);
    bool isLeaf = (!root->left) && (!root->right);
    if ((nowSum == sum) && isLeaf) {
      ans.push_back(curLine);
    }
    if (root->left)
      checkNowLevel(root->left, sum, nowSum, ans, curLine);
    if (root->right)
      checkNowLevel(root->right, sum, nowSum, ans, curLine);
    curLine.pop_back();
  }
};
#endif // LEETCODE_34_H
